Surya Mathialagan

Introduction

Hi! I am Surya, and I am currently a Research Fellow at the Simons Institute in UC Berkeley. I will be starting as a postdoctoral researcher at NTT Research (CIS Lab) in the fall. I am broadly interested in algorithms and theoretical cryptography.

Until recently, I was a PhD student in the MIT Theory group where I was extremely fortunate to be advised by Vinod Vaikuntanathan and Virginia Vassilevska Williams.

In my free time, I enjoy art, dancing, and playing music.

Home

Publications

In all of the works, authors are ordered alphabetically by last name as is the norm in both mathematics and theoretical computer science.

Incrementally Verifiable Computation for NP from Standard Assumptions

Pratish Datta, Abhishek Jain, Zhengzhong Jin, Alexis Korb, Surya Mathialagan, Amit Sahai

Crypto 2025

Simple and General Counterexamples for Private-Coin Evasive LWE

Nico Döttling, Abhishek Jain, Giulio Malavolta, Surya Mathialagan, Vinod Vaikuntanathan

Crypto 2025

[eprint]

Pseudorandom Obfuscation and Applications

Pedro Branco, Nico Döttling, Abhishek Jain, Giulio Malavolta, Surya Mathialagan, Spencer Peters, Vinod Vaikuntanathan

Crypto 2025

[eprint]

Universal SNARGs for NP from Proofs of Correctness

Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Surya Mathialagan

STOC 2025

[eprint] [proceedings] [CMU Talk] [STOC Recorded Talk]

Adaptively Sound Zero-Knowledge SNARKs for UP

Surya Mathialagan, Spencer Peters, Vinod Vaikuntanathan

Crypto 2024

[eprint] [proceedings] [slides]

Towards Optimal Output-Sensitive Clique Listing
or: Listing Cliques from Smaller Cliques

Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu

STOC 2024

[arxiv] [proceedings] [slides]

Memory Checking for Parallel RAMs

Surya Mathialagan

TCC 2023

Best Young Researcher Award, Invited to Journal of Cryptology

[eprint] [proceedings] [TCC talk]

MacORAMa: Optimal Oblivious RAM with Integrity

Surya Mathialagan, Neekon Vafa

Crypto 2023

[eprint] [proceedings] [CMU talk] [Crypto talk] [slides]

Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu

ICALP 2022

[arxiv] [proceedings]

Distinct Distances between Non-Ruled Surfaces and between Circles

Surya Mathialagan, Adam Sheffer

Discrete & Computational Geometry, Volume 69, Issue 2, 2023

[arxiv] [journal]

On Bipartite Distinct Distances in the Plane

Surya Mathialagan

The Electronic Journal of Combinatorics, Volume 28, Issue 4, 2022

[arxiv] [journal]

Tromino Tiling

Liu Hang, Surya Mathialagan, Sean Pek

Mathematical Medley, Volume 40, 2014

[publication]

Manuscripts

On Succinct Obfuscation via Propositional Proofs

Abhishek Jain, Zhengzhong Jin, Surya Mathialagan, Omer Paneth

In submission

[Simons Institute Talk]

A Note on the Conditional Optimality of Chiba and Nishizeki's Algorithms

Yael Kirkpatrick, Surya Mathialagan

Preprint

[arxiv]

Art